package com.example.springbootdemo.suanfa;


import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class SuanFaDemo1 {
    /**
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[0,1]
     * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/two-sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static int[] twoSum(int[] nums, int target) {
        int[] ints = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int i1 = i + 1; i1 < nums.length; i1++) {
                int i2 = nums[i] + nums[i1];
                if (i2 == target) {
                    ints[0] = i;
                    ints[1] = i1;
                }
            }
        }
        return ints;
    }


    public int[] twoSum1(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            } else {
                map.put(nums[i], i);
            }
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(7);
        ListNode next = listNode1.next = new ListNode(8);
        next.next = new ListNode(9);

        ListNode listNode2 = new ListNode(7);
        ListNode next2 = listNode2.next = new ListNode(8);

        next2.next = new ListNode(9);
        ListNode listNode = addTwoNumbers(listNode1, listNode2);
        System.out.println(listNode.toString());

    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode returnList = new ListNode(0);
        ListNode q = returnList;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            int sum = a + b + carry;
            carry = sum > 9 ? 1 : 0;
            q = q.next = new ListNode(sum % 10);
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
            if (carry == 1) {
                q.next = new ListNode(1);
            }
        }
        return returnList;
    }

    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "ListNode{" + "val=" + val + ", next=" + next + '}';
        }
    }

    public static ListNode addTwoNumbers123(ListNode l1, ListNode l2) {
        ListNode returnMap = new ListNode(0);
        ListNode re1 = returnMap;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            int sum = a + b + carry;
            carry = sum > 9 ? 1 : 0;
            re1 = re1.next = new ListNode(sum % 10);
            if (carry == 1) {
                re1.next = new ListNode(carry);
            }
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        return returnMap.next;
    }
}
